﻿// 303 石子合并2.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <memory.h>

using namespace std;
/*
http://oj.daimayuan.top/course/5/problem/201
有 n堆石子围成一个圈，第 i堆石子有 ai颗，
 每次我们可以选择相邻的两堆石子合并，代价是两堆石子数目的和，
 现在我们要一直合并这些石子，使得最后只剩下一堆石子，问总代价最少是多少？

输入格式
第一行一个数字 n。

接下来一行 n个整数 a1,a2,…,an。

输出格式
一行一个整数，表示答案。

样例输入
3
1 3 2
样例输出
9
数据规模
对于所有数据，保证 1≤n≤250,1≤ai≤500。
*/

const int N = 510;
int arr[N * 2],preSum[N*2];
int dp[N * 2][N * 2];
int n;


int solve(int l, int r) {
	if (l == r) { dp[l][r] = 0; return 0; }
	int& res = dp[l][r];
	if (res != 0x3f3f3f3f) return res;

	for (int i = l; i <= r - 1; i++) {
		res = min(res, solve(l, i) + solve(i + 1, r));
	}

	res += preSum[r]-preSum[l-1];
	return res;
}



int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i]; arr[i + n] = arr[i];
	}
	for (int i = 1; i <= 2 * n; i++) {
		preSum[i] = preSum[i - 1] + arr[i];
	}
	memset(dp,0x3f,sizeof dp);
	int ans = 0x3f3f3f3f;
	for (int i = 1; i <= n - 1; i++) {
		ans = min (ans,solve(i,i+n-1));
	}

	cout << ans << endl;

	return 0;
}

 